/* 
    桶排序：针对非负数
*/
var bucketSort = function (arr) {
    if (arr.length < 2) return;
    return bSort(arr, 0, arr.length - 1);
};

function bSort(arr, start, end) {
    let bigestNum = 0;
    let digit = 0;
    let bucket = new Array(10).fill(0);
    let tempArr = new Array(arr.length);
    for (let index = 0; index < arr.length - 1; index++) {
        const element = arr[index];
        if (element > bigestNum) bigestNum = element;
    }
    // 计算最大值位数
    while (bigestNum >= 1) {
        bigestNum = bigestNum / 10;
        digit++;
    }
    // 进行排序

    for (let iteration = 0; iteration < digit; iteration++) {
        let division = Math.pow(10, iteration);
        arr.forEach((element) => {
            // 求第digit位上数字，并且累计
            let num = Math.floor(element / division) % 10;
            // console.log(bucket);
            bucket[num]++;
        });

        for (let index = 0; index < 9; index++) {
            bucket[index + 1] = bucket[index] + bucket[index + 1];
        }

        for (let index = arr.length - 1; index >= 0; index--) {
            const element = arr[index];
            let num = Math.floor(element / division) % 10;
            tempArr[--bucket[num]] = element;
        }
        console.log(tempArr);
        arr = [...tempArr];
        // console.log(tempArr);
        bucket.fill(0);
    }
    return arr;
}
let arr = [1, 6, 9, 6, 96, 56, 6, 56, 456, 6, 465455, 4, 5, 4, 100, 2, 45, 45, 23, 56, 89];
let res = bSort(arr);
console.log(res);
